Randomisierte Algorithmen

Beschreibung:
Nehmen wir an, daß es jedes Jahrtausend mindestens einen Meteoriteneinschlag gibt, der mehr als 100 Quadratmeter der Erdoberfläche verwüstet. Dann läßt sich folgern, daß ein Rechner während einer Mikrosekunde seines Daseins mit einer Wahrscheinlichkeit von mindestens $2^-100$ zerstört wird. Von diesem Standpunkt aus erscheint ein Algorithmus, der mit Fehlerwahrscheinlichkeit kleiner $2^-100$ in Sekundenschnelle $2^400-593$ als die größte Primzahl kleiner $2^400$ identifiziert als sehr praktisch (insbesondere in Bezug auf dahinterstehende, kryptologische Anwendungen). Ein randomisierter Algorithmus ist ein Algorithmus, dessen Verhalten in jedem Schritt von einem Zufallsexperiment (Münzwurf) abhängen kann. Da sich randomisierte Algorithmen nicht mehr deterministisch verhalten, können die Laufzeit und/oder die Korrektheit nur noch mit gewissen Wahrscheinlichkeiten garantiert werden. Es gibt zwei grundsätzliche Vorteile randomisierter Algorithmen: Sie sind oft effizienter und zudem einfacher zu verstehen und zu implementieren als normale (deterministische) Algorithmen. In der Vorlesung werden grundlegende randomisierte Algorithmen für verschiedenste Anwendungen vorgestellt. Zudem werden randomisierte Komplexitätsklassen betrachtet und Methoden und Werkzeuge für die Analyse randomisierter Algorithmen beleuchtet.

Voraussetzungen:
Grundstudium

Literatur:

1. R. Motwani and P. Raghavan Randomized Algorithms. Cambridge University Press, 1995.

Zurück zur Übersicht